#include <bits/stdc++.h>
using namespace std;

#define int long long

//欧拉公式： n * (p1 - 1) / p1 * (p2 - 1) / p2 ......
//可以用容斥原理证明
int eulerFunction(int n) {
    if (n == 1) return 1LL;
    int res = n, now = n;
    //巧妙的点，i * i <= now可以将时间复杂度降至sqrt(n)
    //每次都除最小质因数
    for (int i = 2; i <= now / i; i++) {
        if (now % i == 0) {
            while ((now % i) == 0) {
                now /= i;
            }
            res = res / i * (i - 1);
        }
    }
    if (now > 1) {
        res = res / now * (now - 1);
    }
    return res;
}   

signed main() {
    int n;
    cout << "输入n，你将得到1-n中与n互质的数的个数" << endl;
    cout << "输入n：";
    cin >> n;
    cout << "cnt = " << eulerFunction(n) << endl;
    return 0;
}